package com.example.algorithm.kmp;

/**
 * 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
 *
 *  示例 1:
 * 输入: "abab"
 * 输出: True
 * 解释: 可由子字符串 "ab" 重复两次构成。
 *
 *  示例 2:
 * 输入: "aba"
 * 输出: False
 *
 *  示例 3:
 * 输入: "abcabcabcabc"
 * 输出: True
 * 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 */
public class Leetcode459_RepeatedSubstringPattern {
    public static void main(String[] args) {
        String str = "abcabcabcabc";
//        str = "aabbaabb";
        str = "a";
        str ="abab";
        System.out.println(new Solution().repeatedSubstringPattern(str));

    }

    static class Solution {

        /**
         * 解法三:字符串匹配
         * 思路:
         * 满足条件的字符串一定可以写成如下格式
         * s's' ... s's' (n个)
         * 那么把第一个s'(记为s'')移到末尾得到s'...s's's''该字符串一定和原字符串相同
         *
         * 想要不通过枚举实现:
         *   将两个 s 连在一起，并移除第一个和最后一个字符，判断得到的字符串是否包含 s(KMP实现)，即 s是它 (s+s(1,2n-1)的一个子串。
         * @param s
         * @return
         */
        private boolean repeatedSubstringPattern3(String s) {
            String str = s + s;
            char[] chars = str.toCharArray();
            char[] pattern = s.toCharArray();
            return kmp(chars, pattern) != -1;
        }

        /**
         * 解法二:字符串匹配
         * 思路:
         * 满足条件的字符串一定可以写成如下格式
         * s's' ... s's' (n个)
         * 那么把第一个s'(记为s'')移到末尾得到s'...s's's''该字符串一定和原字符串相同
         *
         * 想要不通过枚举实现:
         *   将两个 s 连在一起，并移除第一个和最后一个字符，判断得到的字符串是否包含 s，即 s是它 (s+s(1,2n-1)的一个子串。
         * @param s
         * @return
         */
        private boolean repeatedSubstringPattern2(String s) {
            // 方式一
//            String str = s + s;
//            return str.substring(1, str.length() - 1).contains(s);
            // 方式二
            return (s + s).indexOf(s, 1) != s.length();
        }

        /**
         * 暴力法
         * 枚举所有可能性
         *
         * 如果一个长度为 n的字符串 s 可以由它的一个长度为 m的子串 ss 重复多次构成，那么：
         *   n 一定是 m 的倍数；
         *   ss 一定是 s 的前缀；
         *   有 s[i]=s[i−m] (m <= i < n)。
         *
         * @param s
         * @return
         */
        private boolean repeatedSubstringPattern1(String s) {
            int len = s.length();
            if (len <= 1) return false;
            char[] chars = s.toCharArray();
            boolean res = false;
            // 暴力法方式一
            for (int subLen = 1; subLen <= len / 2; subLen++) { // 长度从1 ~ len / 2遍历
                if (len % subLen != 0) // 字符长度不能被子串长度不能整除的子串一定不可能是由该子串重复多次组成的字符串
                    continue;

                int maybeCount = len / subLen; // 可能重复的次数
                int j = 1;
                boolean isMatched = true;
                // 一段一段进行比较
                while (j < maybeCount && isMatched) {
                    for (int k = 0; k < subLen; k++) {
                        if (chars[k] != chars[j * subLen + k]) {
                            isMatched = false;
                            break;
                        }
                    }
                    j++;
                }

                if (isMatched) {
                    res = true;
                    break;
                }
            }

            // 方式二(s[i]=s[i−m] (m <= i < n , m为子串长度))
//            for (int subLen = 1; subLen <= len / 2; subLen++) { // 长度从1 ~ len / 2遍历
//                if (len % subLen == 0) {// 字符长度不能被子串长度不能整除的子串一定不可能是由该子串重复多次组成的字符串
//                    boolean isMatched = true;
//                    for (int j = subLen; j < len; j++) {
//                        if (chars[j] != chars[j - subLen]) {
//                            isMatched = false;
//                            break;
//                        }
//                    }
//
//                    if (isMatched) {
//                        res = true;
//                        break;
//                    }
//                }
//            }
            return res;
        }

        private int kmp(char[] chars, char[] pattern) {
            int[] nexts = getNexts(pattern);
            int pos = -1;
            int i = 1, j = 0;
            // 在不包含头尾的字符串chars里 匹配pattern
            while (i < chars.length - 1 && j < pattern.length) {
                if (chars[i] == pattern[j]) {
                    i++;
                    j++;
                } else {
                    if (nexts[j] == -1) {
                        i++;
                        j = 0;
                    } else {
                        j = nexts[j];
                    }
                }

                if (j == pattern.length) {
                    pos = i - j;
                }
            }
            return pos;
        }

        private int[] getNexts(char[] pattern) {
            int[] nexts = new int[pattern.length];
            int j = 0;// 模式串下标 后缀
            int k = -1;// 模式串前缀下标 也是前后缀匹配的长度
            nexts[0] = -1;// 0位置前面没有字符了，所以默认存-1
            int len = pattern.length;
            while (j < len - 1) {//模式串下标未到达最后一个位置
                if (k == -1 || pattern[k] == pattern[j]) {
                    // 到达模式串开头或者匹配成功，则移动到下一位置
                    k++;// 模式串前缀下标移动到下一位置
                    j++;// 模式串移动到下一位置
                    nexts[j] = k;// 把当前k值存放到next数组中
                } else {// 不匹配时，需要对k进行回溯
                    k = nexts[k];// 使用next来找不匹配时的下一个移动位置
                }
            }
            return nexts;
        }

        public boolean repeatedSubstringPattern(String s) {
            return repeatedSubstringPattern1(s);
        }
    }
}
